//检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。 
//
// 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。 
//
// 注意：此题相对书上原题略有改动。 
//
// 示例 1： 
//
// 
// 输入：t1 = [1, 2, 3], t2 = [2]
// 输出：true
// 
//
// 示例 2： 
//
// 
// 输入：t1 = [1, null, 2, 4], t2 = [3, 2]
// 输出：false
// 
//
// 提示： 
//
// 
// 树的节点数目范围为 [0, 20000]。 
// 
//
// Related Topics 树 深度优先搜索 二叉树 字符串匹配 哈希函数 👍 90 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 00:09:56
 * @description 面试题 04.10.检查子树
 */
public class CheckSubtreeLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CheckSubtreeLcci fun=new CheckSubtreeLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

///  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
         // 判断一棵树是否是另一棵树的子树
    // 如果两棵树的结构和节点值都相同，则返回 true，否则返回 false
    //1.有没有办法可以计算出一棵树的哈希值，然后遍历另一棵树，判断他的节点子树的哈希值是否和t2的哈希值相等
    //2.对每个节点与 t2 的根节点进行比较，如果相等，则进一步比较它们的子树，当相等时返回
    //
    public boolean checkSubTree1(TreeNode t1, TreeNode t2) {
        if(t2==null) return true;
        if(t1==null) return false;
        return dfs(t1,t2) || checkSubTree1(t1.left, t2) || checkSubTree1(t1.right, t2);
    }
    private boolean dfs(TreeNode t1, TreeNode t2){
        if(t1==null && t2==null) return true;
        if(t1==null || t2==null) return false;
        if(t1.val != t2.val) return false;
        return dfs(t1.left, t2.left) && dfs(t1.right, t2.right);

    }

    public boolean checkSubTree(TreeNode root, TreeNode subRoot) {
        int hs = getHeight(subRoot);
        return dfs1(root, subRoot, hs).getValue();
    }

    // 代码逻辑同 104. 二叉树的最大深度
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH, rightH) + 1;
    }

    // 100. 相同的树
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q; // 必须都是 null
        }
        return p.val == q.val &&
                isSameTree(p.left, q.left) &&
                isSameTree(p.right, q.right);
    }

    // 返回 node 的高度，以及是否找到了 subRoot
    private Pair<Integer, Boolean> dfs1(TreeNode node, TreeNode subRoot, int hs) {
        if (node == null) {
            return new Pair<>(0, false);
        }
        Pair<Integer, Boolean> left = dfs1(node.left, subRoot, hs);
        Pair<Integer, Boolean> right = dfs1(node.right, subRoot, hs);
        if (left.getValue() || right.getValue()) {
            return new Pair<>(0, true);
        }
        int nodeH = Math.max(left.getKey(), right.getKey()) + 1;
        return new Pair<>(nodeH, nodeH == hs && isSameTree(node, subRoot));
    }
    public class Pair<S, T> {
        private final S first;
        private final T second;

        public Pair(S first, T second) {
            this.first = first;
            this.second = second;
        }

        public S getKey() {
            return first;
        }

        public T getValue() {
            return second;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
